﻿package list;

import common.Node;

public class 删除单链表倒数第k个节点 {

	public static Node removeKth(Node head, int kth) {
		if (head == null || kth <= 0)
			return head;

		Node cur = head;
		while (cur != null) {
			kth--;
			cur = cur.next;
		}
		if (kth == 0) {
			head = head.next;// 说明倒数第k个节点就是头节点
		}
		if (kth < 0) {
			// 如果>0，则存在倒数第k个节点
			// 此时k = N-k;
			cur = head;
			while (++kth != 0) {
				cur = cur.next;
			}
			cur.next = cur.next.next;
		}
		return cur;
	}

	public static void main(String[] args) {
		Node head0 = new Node(1);
		Node head1 = new Node(2);

		Node head2 = new Node(3);
		Node head3 = new Node(4);
		Node head5 = new Node(5);
		Node head4 = new Node(7);

		head3.next = head5;
		head2.next = head3;
		head1.next = head2;

		Node res = removeKth(head1, 2);

		while (res != null) {
			System.out.print(res.value + "");
			res = res.next;
		}
	}
}
